package sort

import (
	"math/rand"
	"time"
)

// 对arr[l...r]部分进行partition操作
// 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
func __partition(arr []int, l, r int) int {
	arr[l], arr[rand.Intn(r-l+1)+l] = arr[rand.Intn(r-l+1)+l], arr[l]
	v := arr[l]
	j := l
	// arr[l+1...j] < v ; arr[j+1...i) > v
	for i := l+1; i <= r; i++ {
		if arr[i] < v {
			j++
			arr[i], arr[j] = arr[j], arr[i]
		}
	}
	arr[l], arr[j] = arr[j], arr[l] // 中间位置交换
	return j
}

func __partition2(arr []int, l, r int) int {
	arr[l], arr[rand.Intn(r-l+1)+l] = arr[rand.Intn(r-l+1)+l], arr[l]
	v := arr[l]
	// arr[l+1...i) <= v; arr(j...r] >= v
	i := l+1
	j := r
	for {
		// 注意这里的边界, arr[i] < v, 不能是arr[i] <= v
		for i <= r && arr[i] < v {
			i++
		}
		// 注意这里的边界, arr[j] > v, 不能是arr[j] >= v
		for j >= l+1 && arr[j] > v {
			j--
		}
		if i > j {
			break
		}
		arr[i], arr[j] = arr[j], arr[i]
		i++
		j--
	}
	arr[l], arr[j] = arr[j], arr[l]
	return j
}

func __quickSort(arr []int, l, r int) {
	if r - l <= 15 {
		InsertSortAdvance(arr[l:r+1])
		return
	}
	p := __partition(arr, l, r)
	__quickSort(arr, l, p-1)
	__quickSort(arr, p+1, r)
}

func __quickSort2(arr []int, l, r int) {
	if r - l <= 15 {
		InsertSortAdvance(arr[l:r+1])
		return
	}
	p := __partition2(arr, l, r)
	__quickSort2(arr, l, p-1)
	__quickSort2(arr, p+1, r)
}

func QuickSort(arr []int) {
	rand.Seed(time.Now().Unix())
	n := len(arr)
	__quickSort(arr, 0, n - 1)
}

func QuickSort2(arr []int) {
	rand.Seed(time.Now().Unix())
	n := len(arr)
	__quickSort2(arr, 0, n - 1)
}

